public class Linkedlist {
    /*1.首先得知道单链表最基础的概念，单链表是由一个一个节点构成的  每个节点由数值域和节点域组成
    * 2.还要知道节点是怎么创建的  将节点通过类 ListNode 来抽象出来   new一个就有一个节点
    * 3.数值域的类型为数值类型 节点域为节点类型  Person p=new Person()  LNode node = new Lnode()
    * 4.创建一个节点类型的头结点引用来表示出那个节点是第一个节点
    * */
    public ListNode head;
    public ListNode cur;

    //最垃圾的第一步，通过穷举法创建一个链表出来
    //1.1通过实例化节点类来创建节点
    public void createList(){
        ListNode listnode1 = new ListNode(11);
        ListNode listnode2 = new ListNode(22);
        ListNode listnode3 = new ListNode(33);
        ListNode listnode4 = new ListNode(44);

        //1.2将节点通过next串起来  如果下面这句代码不写在函数里面会报错
        listnode1.next = listnode2;
        listnode2.next = listnode3;
        listnode3.next = listnode4;
        //1.3 将listnode1这个引用 引用的对象赋值给head
        this.head = listnode1;
    }

    //2.1.节点创建成功之后需要打印出来看看 需要用到循环->使用什么循环 while循环
    //2.2 循环的各种条件是啥->节点的地址不为空
    public void display(){
        this.cur=this.head;
        while(this.cur!=null){
            System.out.print(this.cur.val+" ");
            this.cur=this.cur.next;
        }
    }

    //3 得到单链表的长度
    public int size(){
        int count=0;
        //不要像这样重定义  ListNode cur = this.head;
        this.cur = this.head;
        while(this.cur != null){
            count++;
            this.cur = this.cur.next;
        }
        return count;
    }


    //4.头插法
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        //先绑定后面的节点 即将head节点的地址赋给新插入的头结点的next域
        node.next = this.head;
        head = node;
    }

    //5.尾插法
    public void addLast(int data){
        ListNode node = new ListNode(data);

        //如果链表为空  cur.next就会导致空指针异常
        if(this.head == null){
            head = node;
        }else{
            this.cur = this.head;
            while(cur.next != null){
                this.cur = this.cur.next;
            }
            this.cur.next = node;
        }
    }

    //6.任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        if(index<0 || index>size()){
            System.out.println("你输入的位置有误，请重新输入");
            return;
        }
        if(index==0){
            addFirst(data);
        }
        if(index==size()){
            addLast(data);
        }

        ListNode cur = findIndexSubOne(index);
        ListNode node = new ListNode(data);
        //先把后面的节点绑上
        node.next = cur.next;
        //再把前面的节点绑上
        cur.next = node;
        return;
    }

    //6.1 找到要插入的下标位置的节点
    public ListNode findIndexSubOne(int index) {
        this.cur = this.head;
        for (int i = 0; i < index-1; i++) {
            this.cur = this.cur.next;
        }
        return this.cur;
    }
    //7.查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        this.cur = this.head;
        while (cur!=null){
            if(this.cur.val == key){
                return true;
            }
            this.cur = this.cur.next;
        }
        return false;
    }
    //8.回收所有节点，涉及到内存泄露问题
    public void clear(){
        //有两种方法，一种粗暴方法
        //this.head = null;
        //第二种方法，一个一个置空 需要创建一个curNext引用
        this.cur = this.head;
        while(cur!=null){
            ListNode curNext = this.cur.next;
            this.cur = null;
            this.cur = curNext;
        }
        this.head = null;
        return;
    }

    /*
    //删除第一次出现关键字为key的节点
    public void remove(int key);
    //删除所有值为key的节点
    public void removeAllKey(int key);
    */


}
